package main

import (
	"fmt"
)

func main() {

	numbers := []int{14, 33, 27, 10, 35, 19, 42, 44}
	fmt.Printf("%v\n", numbers)
	numbers = MergeSort(numbers)
	fmt.Printf("%v\n", numbers)

}

func MergeSort(numbers []int) []int {
	length := len(numbers)
	//数组不可再分
	if length <= 1 {
		return numbers
	}
	//评分两个数组。
	mid := length / 2
	//递归进行，持续分割
	array1, array2 := MergeSort(numbers[0:mid]), MergeSort(numbers[mid:length])
	//分组完成，合并分组数据
	return Merge(array1, array2)

}

func Merge(array1, array2 []int) []int {
	len1 := len(array1)
	len2 := len(array2)

	//获取数据长度
	lmax := len1
	if lmax < len2 {
		lmax = len2
	}

	if lmax < 1 {
		return array1
	}

	var ret []int
	//需要合并数组元素下标
	index1 := 0
	index2 := 0
	for true {
		if index2 >= len2 && index1 >= len1 {
			//所有数据排序完毕，退出循环
			break
		}
		if index1 < len1 && index2 < len2 {
			// 两个数组 同时存在元素
			if array1[index1] < array2[index2] {
				ret = append(ret, array1[index1])
				index1++
			} else {
				ret = append(ret, array2[index2])
				index2++
			}
		} else if index1 < len1 {
			//array1 单独存在元素
			ret = append(ret, array1[index1])
			index1++
		} else if index2 < len2 {
			//array2 单独存在元素
			ret = append(ret, array2[index2])
			index2++
		}
	}
	return ret
}
